package algorithm.leetcode

object Fiblacy {
    /**
     * 0, 1, 1, 2, 3
     */
    fun fib(n: Int): Int {
        if(n < 2) return n
        val ir = IntArray(n + 1)
        ir[0] = 0
        ir[1] = 1
        var i = 2

        while (i <= n){
            ir[i] = ir[i-2] + ir[i-1]
            ir[i] %= 1000000007
            i++
        }
        return ir[i-1]
    }
}

fun main() {
    println(Fiblacy.fib(1000000))
}